//
// Created by mazaiting on 2024/4/27.
//

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct DLinkNode                    //双链表结点类型
{
    T data;                        //存放数据元素
    DLinkNode<T> *next;                         //指向后继结点的指针
    DLinkNode<T> *prior;                         //指向前驱结点的指针
    DLinkNode() : next(NULL), prior(NULL) {}            //构造函数
    explicit DLinkNode(T d) : data(d), next(NULL), prior(NULL) {}      //重载构造函数
};

template<typename T>
class CDLinkList          //循环双链表类模板
{
public:
    DLinkNode<T> *dhead;      //循环双链表头结点
    CDLinkList()          //构造函数,创建空表
    {
        dhead = new DLinkNode<T>();
        dhead->next = dhead;      //构成循环的空链表
        dhead->prior = dhead;
    }

    ~CDLinkList()          //析构函数,销毁
    {
        DLinkNode<T> *pre, *p;
        pre = dhead;
        p = pre->next;
        while (p != dhead)          //p遍历并释放前驱结点
        {
            delete pre;             // 释放pre结点
            pre = p;
            p = p->next;      //pre,p同步后移一个结点
        }
        delete pre;          //此时释放尾结点
    }
    //基本运算算法
};

template<typename T>
bool Symm(CDLinkList<T> &L)        //求解算法
{
    bool flag = true;            //flag表示L是否对称，初始时为真
    DLinkNode<T> *p = L.dhead->next;    //p指向首结点
    DLinkNode<T> *q = L.dhead->prior;    //q指向尾结点
    while (flag) {
        if (p->data != q->data)        //对应结点值不相同，置flag为假
            flag = false;
        else {
            if (p == q || p == q->prior)    //满足结束条件退出循环
                break;
            q = q->prior;            //q前移一个结点
            p = p->next;            //p后移一个结点
        }
    }
    return flag;
}

